//https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=23271&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思路1:1.计算cnt次数，如果cnt为0，就选取当前这个数字为ans，
//若cnt不为0，则跟ans相同加上，否则减去1；
//这样我们得到的ans，一定是我们的答案

#include <iostream>
#include <vector>
using namespace std;

class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int> nums) {
        int ans, cnt = 0;
        for (const auto& it : nums) { //遍历nums中的每一个元素
            if (cnt == 0) { //如果当前计数为0，则选取当前值为新答案
                cnt = 1;
                ans = it; //更新答案
            } else {
                if (ans == it)cnt++; //遇到跟当前答案相同的数
                else cnt--;//遇到一个非答案的数
            }
        }
        return ans;//直接返回
    }
};